<!DOCTYPE html>
<html lang="zh-CN">
<head>
    <meta charset="UTF-8">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>二叉树的序列化与反序列化 | 算法可视化</title>
    <link href="https://cdn.staticfile.org/font-awesome/6.4.0/css/all.min.css" rel="stylesheet">
    <link href="https://cdn.staticfile.org/tailwindcss/2.2.19/tailwind.min.css" rel="stylesheet">
    <link href="https://fonts.googleapis.com/css2?family=Noto+Serif+SC:wght@400;500;600;700&family=Noto+Sans+SC:wght@300;400;500;700&display=swap" rel="stylesheet">
    <script src="https://cdn.jsdelivr.net/npm/mermaid@latest/dist/mermaid.min.js"></script>
    <style>
        body {
            font-family: 'Noto Sans SC', 'Noto Serif SC', Tahoma, Arial, Roboto, "Droid Sans", "Helvetica Neue", "Droid Sans Fallback", "Heiti SC", "Hiragino Sans GB", Simsun, sans-serif;
            color: #333;
            line-height: 1.6;
        }
        .hero-gradient {
            background: linear-gradient(135deg, #6e8efb 0%, #a777e3 100%);
        }
        .code-block {
            background: linear-gradient(to right, #f5f7fa, #e4e8eb);
            border-left: 4px solid #6e8efb;
        }
        .card-hover {
            transition: all 0.3s ease;
            box-shadow: 0 4px 6px rgba(0, 0, 0, 0.05);
        }
        .card-hover:hover {
            transform: translateY(-5px);
            box-shadow: 0 10px 15px rgba(0, 0, 0, 0.1);
        }
        .concept-node {
            transition: all 0.3s ease;
        }
        .concept-node:hover {
            transform: scale(1.05);
        }
        .drop-cap::first-letter {
            float: left;
            font-size: 3.5em;
            line-height: 0.8;
            margin: 0.1em 0.1em 0 0;
            color: #6e8efb;
        }
    </style>
</head>
<body class="bg-gray-50">
    <!-- Hero Section -->
    <section class="hero-gradient text-white py-20 px-6">
        <div class="max-w-4xl mx-auto">
            <h1 class="text-4xl md:text-5xl font-bold mb-4 leading-tight">二叉树的序列化与反序列化</h1>
            <p class="text-xl md:text-2xl font-light mb-8 opacity-90">探索数据结构转换的艺术与算法之美</p>
            <div class="flex flex-wrap gap-4">
                <span class="px-4 py-2 bg-white bg-opacity-20 rounded-full text-sm font-medium backdrop-blur-sm">#DFS</span>
                <span class="px-4 py-2 bg-white bg-opacity-20 rounded-full text-sm font-medium backdrop-blur-sm">#BFS</span>
                <span class="px-4 py-2 bg-white bg-opacity-20 rounded-full text-sm font-medium backdrop-blur-sm">#算法可视化</span>
            </div>
        </div>
    </section>

    <!-- Main Content -->
    <div class="max-w-4xl mx-auto px-6 py-12">
        <!-- Introduction -->
        <section class="mb-16">
            <div class="prose prose-lg max-w-none">
                <p class="drop-cap text-gray-700 leading-relaxed">
                    在计算机科学中，二叉树的序列化与反序列化是一个经典问题。它要求我们将树结构转换为字符串表示，并能从字符串重建原始树结构。这项技术在数据存储、网络传输和算法测试中都有广泛应用。
                </p>
            </div>
        </section>

        <!-- Problem Section -->
        <section class="mb-16">
            <div class="flex items-center mb-6">
                <div class="w-1 h-10 bg-blue-500 mr-4"></div>
                <h2 class="text-2xl font-bold text-gray-800">题目描述</h2>
            </div>
            <div class="bg-white p-6 rounded-xl shadow-sm card-hover">
                <p class="text-gray-700 mb-4">
                    设计一个算法，来序列化和反序列化二叉树。序列化是将数据结构转化为字符串的过程，反序列化是将字符串转化为原始数据结构的过程。
                </p>
                <p class="text-gray-700">
                    你的算法不限制使用何种遍历方法，但要确保一个二叉树可以被序列化为一个字符串并且这个字符串可以被反序列化为原始的树结构。
                </p>
            </div>
        </section>

        <!-- Key Concepts -->
        <section class="mb-16">
            <div class="flex items-center mb-6">
                <div class="w-1 h-10 bg-purple-500 mr-4"></div>
                <h2 class="text-2xl font-bold text-gray-800">核心概念</h2>
            </div>
            <div class="grid md:grid-cols-2 gap-6">
                <div class="bg-white p-6 rounded-xl shadow-sm card-hover">
                    <div class="flex items-center mb-4">
                        <div class="w-10 h-10 rounded-full bg-blue-100 flex items-center justify-center text-blue-500 mr-4">
                            <i class="fas fa-project-diagram"></i>
                        </div>
                        <h3 class="text-xl font-semibold text-gray-800">序列化</h3>
                    </div>
                    <p class="text-gray-700">
                        将树结构转换为字符串表示，通常使用前序、中序或后序遍历。空节点需要用特殊字符表示（如"#"）。
                    </p>
                </div>
                <div class="bg-white p-6 rounded-xl shadow-sm card-hover">
                    <div class="flex items-center mb-4">
                        <div class="w-10 h-10 rounded-full bg-purple-100 flex items-center justify-center text-purple-500 mr-4">
                            <i class="fas fa-code-branch"></i>
                        </div>
                        <h3 class="text-xl font-semibold text-gray-800">反序列化</h3>
                    </div>
                    <p class="text-gray-700">
                        从序列化字符串重建原始树结构，通常使用递归或队列来实现，保持与序列化相同的遍历顺序。
                    </p>
                </div>
            </div>
        </section>

        <!-- Solution Approach -->
        <section class="mb-16">
            <div class="flex items-center mb-6">
                <div class="w-1 h-10 bg-green-500 mr-4"></div>
                <h2 class="text-2xl font-bold text-gray-800">解题思路</h2>
            </div>
            <div class="bg-white p-6 rounded-xl shadow-sm card-hover">
                <h3 class="text-xl font-semibold text-gray-800 mb-3">DFS 前序遍历方案</h3>
                <ul class="list-disc pl-6 space-y-2 text-gray-700">
                    <li><strong>序列化：</strong>使用前序遍历，将节点值序列化为字符串，空节点用特殊字符（如 "#"）表示</li>
                    <li><strong>反序列化：</strong>将字符串分割为列表，使用递归或队列重建树</li>
                </ul>
                <div class="mt-6">
                    <div class="flex items-center mb-3">
                        <i class="fas fa-clock text-gray-500 mr-2"></i>
                        <span class="text-sm font-medium text-gray-600">时间复杂度：O(n)</span>
                        <span class="mx-3 text-gray-400">|</span>
                        <i class="fas fa-memory text-gray-500 mr-2"></i>
                        <span class="text-sm font-medium text-gray-600">空间复杂度：O(n)</span>
                    </div>
                </div>
            </div>
        </section>

        <!-- Code Example -->
        <section class="mb-16">
            <div class="flex items-center mb-6">
                <div class="w-1 h-10 bg-yellow-500 mr-4"></div>
                <h2 class="text-2xl font-bold text-gray-800">示例代码</h2>
            </div>
            <div class="bg-gray-800 rounded-xl overflow-hidden shadow-lg">
                <div class="flex items-center px-4 py-3 bg-gray-700">
                    <div class="flex space-x-2 mr-4">
                        <div class="w-3 h-3 rounded-full bg-red-500"></div>
                        <div class="w-3 h-3 rounded-full bg-yellow-500"></div>
                        <div class="w-3 h-3 rounded-full bg-green-500"></div>
                    </div>
                    <span class="text-sm font-mono text-gray-300">Python 实现 (DFS 前序遍历)</span>
                </div>
                <pre class="p-6 text-gray-100 font-mono text-sm overflow-x-auto"><code>class Codec:
    def serialize(self, root):
        if not root:
            return "#"
        return f"{root.val},{self.serialize(root.left)},{self.serialize(root.right)}"
    
    def deserialize(self, data):
        def dfs():
            val = next(vals)
            if val == "#":
                return None
            node = TreeNode(int(val))
            node.left = dfs()
            node.right = dfs()
            return node
        
        vals = iter(data.split(","))
        return dfs()</code></pre>
            </div>
        </section>

        <!-- Visualization -->
        <section class="mb-16">
            <div class="flex items-center mb-6">
                <div class="w-1 h-10 bg-red-500 mr-4"></div>
                <h2 class="text-2xl font-bold text-gray-800">可视化演示</h2>
            </div>
            <div class="bg-white p-6 rounded-xl shadow-sm card-hover">
                <div class="mermaid">
                    graph TD
                        A[序列化与反序列化] --> B[序列化]
                        A --> C[反序列化]
                        B --> D["前序遍历 (Pre-order)"]
                        B --> E["空节点标记 (#)"]
                        C --> F["迭代器 (Iterator)"]
                        C --> G["递归构建 (DFS)"]
                        D --> H["根节点 → 左子树 → 右子树"]
                        F --> I["按顺序获取节点值"]
                        G --> J["构建左/右子树"]
                </div>
                <div class="mt-6 grid md:grid-cols-2 gap-6">
                    <div>
                        <h3 class="text-lg font-semibold text-gray-800 mb-3">序列化过程</h3>
                        <div class="flex items-center mb-2">
                            <div class="w-4 h-4 rounded-full bg-blue-500 mr-2"></div>
                            <span class="text-sm text-gray-700">根节点</span>
                        </div>
                        <div class="flex items-center mb-2">
                            <div class="w-4 h-4 rounded-full bg-green-500 mr-2"></div>
                            <span class="text-sm text-gray-700">左子树</span>
                        </div>
                        <div class="flex items-center">
                            <div class="w-4 h-4 rounded-full bg-purple-500 mr-2"></div>
                            <span class="text-sm text-gray-700">右子树</span>
                        </div>
                    </div>
                    <div>
                        <h3 class="text-lg font-semibold text-gray-800 mb-3">反序列化过程</h3>
                        <div class="flex items-center mb-2">
                            <div class="w-4 h-4 rounded-full bg-blue-500 mr-2"></div>
                            <span class="text-sm text-gray-700">创建根节点</span>
                        </div>
                        <div class="flex items-center mb-2">
                            <div class="w-4 h-4 rounded-full bg-green-500 mr-2"></div>
                            <span class="text-sm text-gray-700">递归构建左子树</span>
                        </div>
                        <div class="flex items-center">
                            <div class="w-4 h-4 rounded-full bg-purple-500 mr-2"></div>
                            <span class="text-sm text-gray-700">递归构建右子树</span>
                        </div>
                    </div>
                </div>
            </div>
        </section>

        <!-- Performance Analysis -->
        <section class="mb-16">
            <div class="flex items-center mb-6">
                <div class="w-1 h-10 bg-indigo-500 mr-4"></div>
                <h2 class="text-2xl font-bold text-gray-800">性能分析</h2>
            </div>
            <div class="bg-white p-6 rounded-xl shadow-sm card-hover">
                <div class="grid md:grid-cols-3 gap-6 text-center">
                    <div class="p-4 border border-gray-100 rounded-lg">
                        <div class="text-3xl font-bold text-indigo-600 mb-2">O(n)</div>
                        <div class="text-sm font-medium text-gray-500">时间复杂度</div>
                        <p class="text-xs text-gray-600 mt-2">每个节点只访问一次</p>
                    </div>
                    <div class="p-4 border border-gray-100 rounded-lg">
                        <div class="text-3xl font-bold text-indigo-600 mb-2">O(n)</div>
                        <div class="text-sm font-medium text-gray-500">空间复杂度</div>
                        <p class="text-xs text-gray-600 mt-2">递归栈或队列的空间消耗</p>
                    </div>
                    <div class="p-4 border border-gray-100 rounded-lg">
                        <div class="text-3xl font-bold text-indigo-600 mb-2">2n+1</div>
                        <div class="text-sm font-medium text-gray-500">序列化长度</div>
                        <p class="text-xs text-gray-600 mt-2">n个节点需要2n+1个标记</p>
                    </div>
                </div>
            </div>
        </section>
    </div>

    <script>
        mermaid.initialize({
            startOnLoad: true,
            theme: 'default',
            flowchart: {
                useMaxWidth: false,
                htmlLabels: true,
                curve: 'basis',
                nodeSpacing: 50,
                rankSpacing: 70
            }
        });
    </script>
</body>
</html>